;; The first three lines of this file were inserted by DrRacket. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname u5-huebung) (read-case-sensitive #t) (teachpacks ((lib "show-queen.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "show-queen.ss" "teachpack" "htdp")))))
;; 6
;; contract:    n-queens: number -> number
;; description: Calculates all possible solutions of the n-queens problem.
;; example:     (n-queens 8) -> 92

(define (n-queens size)
  (local (
          ;; data definition of a queen
          (define-struct dame (x y))
          
          ;; contract:    neuedame: dame -> dame or false
          ;; description: Erzeugt die nachfolgende dame der übergebenen dame.
          ;; example:     (neuedame (make-dame 1 3) ergibt bei einer Brettgröße von 4 (make-dame 1 4)
          (define (neuedame altedame)
               (cond 
                 [(< size (+ 1 (dame-y altedame))) (cond [(< size (+ 1 (dame-x altedame))) false] 
                                                         [else (make-dame (+ 1 (dame-x altedame)) 1)])]
                 [else (make-dame (dame-x altedame) (+ 1 (dame-y altedame)))]))
          
          
          ;; contract:    dame-okay: dame (listof dame) -> boolean
          ;; description: prüft, ob die Dame existieren darf, wenn die Damen aus der Liste bereits auf dem Feld stehen
          ;; example:     (dame-okay (make-dame 1 2) (list (make-dame 1 1))) -> false
         (define (dame-okay dame vorherigedamen)
           (local (
                   ;; contract:    okay?: dame -> boolean 
                   ;; description: Same as dame-okay
                   ;; example:     (okay? (make-dame 2 3) -> false if dame = (make-dame 2 2)
                   (define (okay? dame2)
                     (cond
                       [(and
                          (not (= (dame-x dame) (dame-x dame2)))
                          (not (= (dame-y dame) (dame-y dame2)))
                          (not (= (- (dame-x dame) (dame-y dame)) (- (dame-x dame2) (dame-y dame2))))
                          (not (= (+ (dame-x dame) (dame-y dame)) (- (dame-x dame2) (dame-y dame2))))) true]
                       [else false])))
             (cond
               [(empty? (list vorherigedamen)) true]
               [else (andmap okay? vorherigedamen)])))
         
         
         ;; contract: queens: dame number listofdamen -> number
         ;; description:
         ;; example:  (queens (make-dame 1 1) 0 (list (make-dame 2 2))) ->
         (define (queens dame zaehler-ergebnisse vorherigedamen)
           (cond
             [(and (empty? vorherigedamen) (and (= (dame-x dame) size) (= (dame-y dame) size))) zaehler-ergebnisse] 
             [(false? dame)                                (queens (neuedame (first vorherigedamen)) zaehler-ergebnisse (rest vorherigedamen))]
             [(false? (dame-okay dame vorherigedamen))     (queens (neuedame dame) zaehler-ergebnisse vorherigedamen)]
             [(equal?  (+ 1 (length vorherigedamen)) size) (queens (first vorherigedamen) (+ 1 zaehler-ergebnisse) (rest vorherigedamen))]
             [else                                         (queens (neuedame dame) zaehler-ergebnisse (append (list dame) vorherigedamen))])))
    
    (queens (make-dame 1 1) 0 empty)))


;; Tests